int singleNonDuplicate(int* nums, int numsSize){
    int i = 0, j = numsSize-1, mid;
    // 数组个数一定是奇数
    // 判断中间值的左右两端是单数还是双数！答案肯定是在单数的那一边！
    while (i < j) {
        mid = (i+j)/2;
        if (nums[mid] == nums[mid+1]) {
            if ((j - mid + 1) % 2 == 0) j = mid-1;    //右边是双数
            else i = mid+2;
        }
        else if (nums[mid] == nums[mid-1]) {
            if ((mid - i + 1) % 2 == 0) i = mid+1;    //左边是双数
            else j = mid-2;
        }
        else return nums[mid];
    }
    return nums[i];    
}